//四数之和
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int n = nums.size();
        //先固定两个数nums[i],nums[j]，通过双指针求解
        vector<vector<int>> ret;
        for(int i = 0 ; i < n ; ++i)
        {
            while(i > 0 && i < n && nums[i-1] == nums[i]) ++i;
            for(int j = i+1 ; j < n ; ++j)
            {
                while(j < n && j > i+1 && nums[j-1] == nums[j]) ++j;
                int begin = j+1;
                int end = n-1;
                while(begin < end)
                {
                    long long sum = static_cast<long long>(nums[i] + nums[j]) + static_cast<long long>(nums[begin] + nums[end]);
                    if(sum < target) ++begin;
                    else if(sum > target) --end;
                    else 
                    {
                        ret.push_back({nums[i],nums[j],nums[begin],nums[end]});
                        ++begin;
                        --end;
                        while(begin < end && nums[begin-1] == nums[begin]) ++begin;
                        while(begin < end && nums[end+1] == nums[end]) --end;
                    }
                }
            }
        }
        return ret;
    }
};

//长度最小的子数组
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0 , right = 0;//left表示滑动窗口的左边界，right表示滑动窗口的右边界
        int n = nums.size() , sum = 0 , ret = INT_MAX;
        while(right < n)
        {
            
            sum += nums[right];
            if(sum >= target)
            {
                ret = min(right - left+1,ret);
                sum -= nums[left];
                ++left;
                sum -= nums[right];
            }
            else 
            {
                right++;
            }
        }
        return ret == INT_MAX ? 0 : ret;
    }
};

//无重复字符的最长子串
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> hash;
        int left = 0 , right = 0 , n = s.size() , len = 0;
        if(s.size() == 1)
            return 1;
        while(right < n)
        {
            if(!hash.count(s[right]))
            {
                hash.insert(s[right]);
            }
            else 
            {
                while(s[left] != s[right]) 
                {
                    hash.erase(s[left]);
                    ++left;
                }
                ++left;
            }
            ++right;
            len = max(right-left,len);

        }
        return len;
    }
};

//最大连续1的个数
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int left = 0 , right = 0 , n = nums.size() , ret = 0;
        while(right < n && nums[right] != 1) ++right;
        left = right;
        while(right < n)
        {
            if(nums[right] == 1) ++right;
            else
            {
                ret = max(right-left, ret);
                while(right < n &&nums[right] != 1) ++right;
                left = right;
            }
        }
        ret = max(right - left, ret);
        return ret;
    }
};

//最大连续1的个数III
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0 ,right = 0 , n = nums.size(),ret = 0,t = k;
        while(right < n)
        {
            if(!nums[right++])--t;
            if(t < 0)
            {
                std::cout << left << " " << right << std::endl;
                ret = max(right - left-1,ret);
                while(left < n && nums[left++]);
                //走到零位置 
                ++t ;
            }
        }
        ret = max(right - left , ret);
        return ret;
    }
};

//将x减到0的最小操作数
class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int n = nums.size();
        int sum = 0;
        for(auto& e : nums)
        {
            sum += e;
        }
        int target = sum - x , len = -1 , left = 0 , right = 0;
        if(target < 0) return -1;
        sum = 0;
        while(right < n)
        {
            sum += nums[right];
            if(sum < target) ++right;
            else if(sum > target)
            {
                sum -= nums[left];
                sum -= nums[right];
                ++left;
            }
            else 
            {
                len = max(right - left+1 , len);
                ++right;
            }

        }
        return len == -1 ? -1 : n-len;
    }
};





